﻿using System;
using System.Collections;
using System.Collections.Generic;

namespace Activity.V
{
	/// <summary>
	/// Демонстрационная программа 5-ой лабораторной работы
	/// </summary>
	public class Program
	{
		protected static AVLTree binaryTree; //		Бинарное дерево
		protected static Random random; //			Генератор случайных чисел

		public static void Main (string[] args)
		{
			// Инициализация
			random = new Random();
			binaryTree = new AVLTree(Comparer<int>.Default);
			Fill(binaryTree, 40);
			DisplayMenu(MenuEntry.Main);
		}

		/// <summary>
		/// Отобразить указанное меню.
		/// </summary>
		/// <param name="menu">Числовое представление активного меню.</param>
		public static void DisplayMenu (MenuEntry menu)
		{
			Console.Clear();
			Console.WriteLine("Лабораторная работа #5");
			Console.WriteLine("Тема: \"Бинарные деревья\"\n");

			// Переходим к следующему меню
			switch (menu)
			{
				case MenuEntry.Main:
					MainMenu();
					break;
				case MenuEntry.Create:
					CreateTreeMenu();
					break;
				case MenuEntry.Fill:
					FillTreeMenu();
					break;
				case MenuEntry.Display:
					PrintTreeMenu();
					break;
				case MenuEntry.Аdd:
					AddTreeValueMenu();
					break;
				case MenuEntry.Remove:
					RemoveTreeValueMenu();
					break;
				case MenuEntry.Balance:
					BalanceTreeMenu();
					break;
				case MenuEntry.Exit:
					// Не переходим к следующему меню
					return;
			}
		}

		/// <summary>
		/// Отобразить главное меню.
		/// </summary>
		private static void MainMenu ()
		{
			Console.WriteLine("Главное Меню");
			Console.WriteLine();
			Console.WriteLine("1. Создать дерево");
			Console.WriteLine("2. Заполнить дерево");
			Console.WriteLine("3. Показать дерево");
			Console.WriteLine("4. Добавление элементов");
			Console.WriteLine("5. Удаление элемента");
			Console.WriteLine("6. Балансировка дерева");
			Console.WriteLine("0. Выход");
			Console.WriteLine();

			var option = ReadInt("Выбор[0-6]: ");
			DisplayMenu(GetMainMenuEntry(option));
		}

		/// <summary>
		/// Преобразовать выбор пользователя в численное представление меню.
		/// </summary>
		/// <param name="option">Значение выбранное пользователем.</param>
		/// <returns>Меню которое необходимо показать.</returns>
		private static MenuEntry GetMainMenuEntry (int option)
		{
			switch (option)
			{
				case 1:
					return MenuEntry.Create;
				case 2:
					return MenuEntry.Fill;
				case 3:
					return MenuEntry.Display;
				case 4:
					return MenuEntry.Аdd;
				case 5:
					return MenuEntry.Remove;
				case 6:
					return MenuEntry.Balance;
				case 0:
					return MenuEntry.Exit;
				default:
					return MenuEntry.Main;
			}
		}

		/// <summary>
		/// Отобразить меню создания дерева.
		/// </summary>
		private static void CreateTreeMenu ()
		{
			Console.WriteLine("Создание Дерева\n");

			int size;
			bool hasValidSize;
			do
			{
				// Считываем размер массива до тех пор пока не будет удовлетворять условиям
				size = ReadInt(string.Format("Введите размера дерева: "));
				hasValidSize = size >= 0;
				if (!hasValidSize) Console.WriteLine("Неверный размер дерева!\n");
			} while (!hasValidSize);

			// Удаляем старые элементы и заполняем новыми.
			binaryTree.Clear();
			Fill(binaryTree, size);

			// Отображаем элементы дерева
			Print(binaryTree);

			ReadLine("\nНажмите клавишу ввода для возврата в главное меню...");
			DisplayMenu(MenuEntry.Main);
		}

		/// <summary>
		/// Отобразить меню заполнения дерева.
		/// </summary>
		private static void FillTreeMenu ()
		{
			Console.WriteLine("Заполнение Дерева\n");

			// Запоминаем размер и очищаем дерево
			var size = binaryTree.Count;
			binaryTree.Clear();

			// Заполняем и отображаем элементы дерева
			Fill(binaryTree, size);
			Print(binaryTree);

			ReadLine("\nНажмите клавишу ввода для возврата в главное меню...");
			DisplayMenu(MenuEntry.Main);
		}

		/// <summary>
		/// Отобразить меню добавления нового элемента в дерево.
		/// </summary>
		private static void AddTreeValueMenu ()
		{
			const char separator = ' ';
			Console.WriteLine("Добавление элементов\n");
			var input = ReadLine(string.Format("Введите множество значений используя '{0}' разделитель: ", separator));
			Console.WriteLine();
			var values = input.Split(separator);
			if (values.Length == 1)
			{
				var value = int.Parse(values[0]);
				// Добавляем элемент
				var node = binaryTree.Add(value);
				// Определяем куда был добавлен новый элемент
				if (node.Parent != null) Console.WriteLine("Элемент {0} добавлен после элемента {1}.", value, node.Parent.Value);
				else Console.WriteLine("Элемент {0} добавлен в корень дерева.", value);
				// Отображаем путь до добавленного элемента
				AVLTree.PrintPath(node);
			}
			else
			{
				// Добавляем все элементы
				foreach (var value in values)
				{
					int i;
					if (int.TryParse(value, out i))
						binaryTree.Add(i);
				}
				// Показываем новое дерево
				Print(binaryTree);
			}

			ReadLine("\nНажмите клавишу ввода для возврата в главное меню...");
			DisplayMenu(MenuEntry.Main);
		}

		/// <summary>
		/// Отобразить меню удаления элемента дерева.
		/// </summary>
		private static void RemoveTreeValueMenu ()
		{
			Console.WriteLine("Удаление элемента\n");
			var value = ReadInt("Введите целочисленное значение для удаления: ");
			Console.WriteLine();

			// Ищем узел который необходимо удалить
			var node = binaryTree.Find(value);
			if (node != null)
			{
				// Запоминаем родительский узел
				var parent = node.Parent;

				Console.WriteLine("Путь до найденного узла:");
				AVLTree.PrintPath(node);

				Console.WriteLine("\nВетка до удаления узла:");
				AVLTree.PrintTree(parent);

				// Запоминаем состояние сбалансированности
				var hasBalance = AVLTree.HasBalance(parent);

				// Удаляем узел
				binaryTree.Remove(node);

				Console.WriteLine("\nВетка после удаления узла:");
				AVLTree.PrintTree(parent);

				// Проверяем изменение состояния сбалансированности с текущим
				if (hasBalance && !AVLTree.HasBalance(parent))
				{
					var color = Console.ForegroundColor;
					Console.ForegroundColor = ConsoleColor.Red;
					Console.WriteLine("\nДерево потеряло балансировку после удаления элемента!");
					Console.ForegroundColor = color;
					Console.WriteLine("Дерево будет автоматически сбалансировано!");

					// Балансируем дерево
					binaryTree.BalanceTree(parent);
				}
			}
			else
				Console.WriteLine("Элемент {0} не найден.", value);

			ReadLine("\nНажмите клавишу ввода для возврата в главное меню...");
			DisplayMenu(MenuEntry.Main);
		}

		/// <summary>
		/// Отобразить меню вывода дерева.
		/// </summary>
		private static void PrintTreeMenu ()
		{
			Console.WriteLine("Вывод Дерева\n");

			// Отображаем элементы массива
			Print(binaryTree);
			ReadLine("\nНажмите клавишу ввода для возврата в главное меню...");
			DisplayMenu(MenuEntry.Main);
		}

		/// <summary>
		/// Отобразить меню балансировки дерева.
		/// </summary>
		public static void BalanceTreeMenu ()
		{
			Console.WriteLine("Балансировка Дерева\n");

			var value = ReadInt("Введите целочисленное значение для удаления: ");
			Console.WriteLine();

			var node = binaryTree.Find(value);
			if (node != null)
			{
				Console.WriteLine("Путь до найденного узла:");
				AVLTree.PrintPath(node);

				Console.WriteLine("\nВетка до балансировки узла:");
				AVLTree.PrintTree(node);

				// Балансировка
				binaryTree.BalanceTree(node);

				Console.WriteLine("\nВетка после балансировки узла:");
				AVLTree.PrintTree(node);
			}
			else
				Console.WriteLine("Элемент {0} не найден.", value);

			ReadLine("\nНажмите клавишу ввода для возврата в главное меню...");
			DisplayMenu(MenuEntry.Main);
		}

		/// <summary>
		/// Заполнить дерево случайными целыми числами.
		/// </summary>
		public static void Fill (AVLTree tree, int size)
		{
			// Создаем список уникальный чисел
			var values = new List<int>(size);
			for (int i = 0; i < size; i++) values.Add(i);

			// Перемешиваем список
			Shuffle(values);

			// Заполняем дерево числами из списка
			foreach (var value in values) tree.Add(value);
		}

		/// <summary>
		/// Вывод элементов дерева на экран.
		/// </summary>
		/// <param name="tree">Экземпляр дерева.</param>
		public static void Print (AVLTree tree)
		{
			Console.WriteLine("Элементы дерева [Кол-во: {0} Высота: {1}/{2}]:", tree.Count, tree.GetHeight(), tree.GetMaxHeight());
			tree.Print();
			Console.WriteLine();
			var hasBalance = tree.HasBalance();
			var consoleColor = Console.ForegroundColor;
			Console.ForegroundColor = hasBalance ? ConsoleColor.Green : ConsoleColor.Yellow;
			Console.WriteLine(hasBalance ? "Дерево сбалансировано" : "Дерево не сбалансировано");
			Console.ForegroundColor = consoleColor;
		}

		/// <summary>
		/// Считать данные введенные пользователем.
		/// </summary>
		/// <param name="message">Приглашение для ввода данных.</param>
		/// <returns>Возвращает текст введенный пользователем.</returns>
		public static string ReadLine (string message)
		{
			Console.Write(message);
			return Console.ReadLine();
		}

		/// <summary>
		/// Считать целое число введенное пользователем.
		/// </summary>
		/// <param name="message">Приглашение для ввода данных.</param>
		/// <returns>Возвращает целое число которое ввел пользователь; в противном случае -1.</returns>
		public static int ReadInt (string message)
		{
			string input = null;
			while (string.IsNullOrWhiteSpace(input))
			{
				Console.Write(message);
				input = Console.ReadLine();
			}
			int retVal;
			if (Int32.TryParse(input, out retVal))
				return retVal;
			return -1;
		}

		/// <summary>
		/// Перемешать оЪьекты внутри списка.
		/// </summary>
		/// <param name="list">Экземпляр списка.</param>
		public static void Shuffle (IList list)
		{
			var count = list.Count;
			while (count > 1)
			{
				count--;
				var i = random.Next(count + 1);
				var value = list[i];
				list[i] = list[count];
				list[count] = value;
			}
		}

		/// <summary>
		/// Перечисление возможных меню для отображения.
		/// </summary>
		public enum MenuEntry
		{
			Main,
			Create,
			Fill,
			Display,
			Аdd,
			Remove,
			Balance,
			Exit,
		}
	}
}
